package analyses;

import graph.HasGraph;

import java.util.Iterator;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Vector;


public class DijkstraComplete {
	//http://www.iti.fh-flensburg.de/lang/algorithmen/graph/dijkstra.htm
	//http://www.iti.fh-flensburg.de/lang/algorithmen/graph/shortest-paths.htm
	//http://en.wikipedia.org/wiki/Dijkstra_algorithm
	
	private HasGraph graph;

	private double[] dist;

	private int[] pred;

	private boolean[] tree;

	private double maxDist;
	
	private double[] centrality;
	
	private double maxCentrality;
	
	int[] traffic;

	
	
	public DijkstraComplete(HasGraph graph_) {
		graph = graph_;
	}
	
	public void computeAllPaths(Vector<Integer> nodes) {
		
		initGraph();
		
		for (int i=0;i< nodes.size()-1;i++){
			int cCentrality=0;
			int startI=nodes.get(i);
			Vector<Integer> s=new Vector<Integer>();
			s.add(startI);
			computeShortestPaths(s);
			for (int j=i;j< nodes.size();j++){
				int endI=nodes.get(j);
				if (endI!=startI){
					//System.out.println(this.getDistance(endI));
					centrality[startI]+=this.getDistance(endI);
					centrality[endI]+=this.getDistance(endI);
				ArrayList<Integer>path=this.getShortestPath(endI);
				for (int ii=0;ii<path.size();ii++){
					int cI=path.get(ii);
					traffic[cI]++;
				}
				}
			}
//			centrality[startI]=cCentrality;
//			if (cCentrality>maxCentrality){
//				maxCentrality=cCentrality;
//			}
		}
		
	}

	public void computeShortestPaths(int s_){
		initGraph();
		Vector<Integer> s=new Vector<Integer>();
		s.add(s_);
		computeShortestPaths(s);
	}
	
	public void initGraph(){
		
		int n = graph.getNodesSize();
		dist = new double[n];
		pred = new int[n];
		tree = new boolean[n];
		traffic=new int[n];
		centrality=new double[n];
		maxCentrality=0;
		
	}
	
	public void initPath(){
		for (int v = 0; v < graph.getNodesSize(); v++) {
			dist[v] = Double.MAX_VALUE;
			pred[v] = -1;
			tree[v] = false;
		}
	}
	
	private void computeShortestPaths(Vector<Integer> startIList) {
		initPath();
		maxDist = 0;
		int u, v;
		double d;
		Iterator<Integer> it;

		PriorityQueue<Pair> pq = new PriorityQueue<Pair>();
		for (int i=0;i<startIList.size();i++){
			int cId=startIList.get(i);
			dist[cId] = 0;
			pq.offer(new Pair(0, cId));
		}

		while (!pq.isEmpty()) {
			u = pq.poll().index;
			if (!tree[u]) {
				tree[u] = true;
				it = graph.getNeighbourIterator(u);
				while (it.hasNext()) {
					v = it.next();
					d = dist[u] + graph.getWeight(u, v); 
					if (d < dist[v]) {
						if (maxDist < d) {
							maxDist = d;
						}
						dist[v] = d;
						pred[v] = u;
						pq.offer(new Pair(d, v));
					}
				}
			}
		}
	}
	

	// distance from node v to startNode
	public double getDistance(int v) {
		return dist[v];
	}

	// predecessor to the node v from tree of shortestpaths
	public int getPredecessor(int v) {
		return pred[v];
	}

//	 sequenze of nodes form node v to startnode from tree of shortestpaths
	public ArrayList<Integer> getShortestPath(int v) {
		ArrayList<Integer> p = new ArrayList<Integer>();
		while (v != -1) {
			p.add(v);
			v = getPredecessor(v);
		}
		return p;
	}

	public double getMaxDist() {
		return maxDist;
	}

	private class Pair implements Comparable {
		double value;
		int index;
		public Pair(double value, int index) {
			this.value = value;
			this.index = index;
		}
		public int compareTo(Object arg0) {
			// TODO Auto-generated method stub
			return Double.compare(value, ((Pair) arg0).value);
		}
	}

	public int[] getTraffic() {
		return traffic;
	}

	public double[] getCentrality() {
		return centrality;
	}
}
